package com.zj.leetcode.medium.greed;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: algorithm
 * @description: 合并区间
 * 56 merge-intervals
 * @author: Zhang Bo
 * @create: 2022-03-23 14:16:26
 **/
public class MergeIntervals {
    public static void main(String[] args) {
//        int[][] intervals = {{1, 3}, {2, 6}, {1, 10}};
//        [[4,5],[1,3],[2,6],[8,10],[15,18],[0,30]]
        int[][] intervals = {{4, 5}, {1, 3}, {2, 6}, {8, 10}, {15, 18}, {0, 30}};
        Solution solution = new MergeIntervals().new Solution();
        System.out.println(Arrays.deepToString(solution.merge(intervals)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {

            if (intervals.length <= 1) {
                return intervals;
            }
            List<int[]> ints =
                    Arrays.stream(intervals)
                            .sorted((a, b) -> {
                                int temp = a[0] - b[0];
                                if (temp == 0) {
                                    return b[1] - a[1];
                                }
                                return temp;
                            }).collect(Collectors.toList());

            List<int[]> ret = new LinkedList<>();
            ret.add(ints.get(0));
            for (int i = 1; i < ints.size(); i++) {
                int[] pre = ret.get(ret.size() - 1);
                int[] after = ints.get(i);
                if (pre[1] >= after[0] && pre[1] < after[1]) {
                    ret.remove(ret.size() - 1);
                    ret.add(new int[]{pre[0], after[1]});
                } else if (pre[0] != after[0] && pre[1] < after[1]) {
                    ret.add(after);
                }
            }

            return ret.toArray(new int[ret.size()][2]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
